import sys
import testutils

def lis(input):
    """Find and return the longest increasing subsequence (LIS) in the given
    list
    Note: This algorithm demonstrates the use of dynamic programming. There is,
    however, a more efficient solution to the LIS problem. See:
    http://en.wikipedia.org/wiki/Longest_increasing_subsequence"""
    
    # pad the list with a -infinity at the beginning
    l = [-sys.maxsize - 1] + input
    n = len(l)
    
    # Allocate an n by n matrix of lists to store results. The i,jth element
    # of M will store the longest incresing subsequence in l[i:], such that
    # every element of the subsequence is greater than l[j]. Padding the 
    # beginning of the list with -infinity is a convenient way to avoid extra
    # processing at the end of this process.
    # Note that only two rows of this matrix are in use at any point, so if
    # we wanted to be more space efficient we could store only two lists.
    M = [[[] for i in range(len(l))] for i in range(len(l))]
    
    for j in range(n):
        if l[j] < l[n-1]:
            M[n-1][j] = [l[n-1]]
        else:
            M[n-1][j] = []
    
    for i in range(n-2, -1, -1):
        for j in range(i+1):
            if l[i] <= l[j]:
                M[i][j] = M[i+1][j]
            else:
                candidate1 = M[i+1][j]
                candidate2 = M[i+1][i]
                if len(candidate1) > len(candidate2) + 1:
                    M[i][j] = candidate1
                else:
                    M[i][j] = [l[i]] + candidate2

    #testutils.print_matrix(M)
    return M[0][0]
        
if __name__ == '__main__':
    seq = []
    if len(sys.argv) > 1:
        for item in sys.argv[1:]:
            seq.append(int(item))
    else:
        seq = [6,4,12,6,2,8,9,7,14]
    
    print("for example, on input:") 
    print(seq)
    print("lis returns:")
    print(lis(seq))